package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * 2216. 美化数组的最少删除数
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/12 14:17
 */
public class MinDeletion {

    public static void main(String[] args) {
        MinDeletion test = new MinDeletion();

        // 2
//        int[] arr = { 1,1,2,2,3,3};

        // 1
        int[] arr = {1, 1, 2, 3, 5};

        int i = test.minDeletion(arr);

        System.out.println(i);
    }

    public int minDeletion(int[] nums) {
        int length = nums.length;
        if (length < 2) {
            return length;
        }
        int[] arra = new int[length];
        int[] arrb = new int[length];
        int last = -1;
        arrb[0] = 1;
        for (int i = 1; i < length; i++) {
            if (nums[i] != nums[i - 1]) {
                last = i - 1;
            }
            arrb[i] = arra[i - 1] + 1;
            arra[i] = Math.max(arra[i - 1], last == -1 ? 0 : arrb[last] + 1);
        }
        return length - arra[length - 1];
    }

}

